UVa/10154 - Weights and measures/10154.cpp

   1 #include <vector>
   2 #include <algorithm>
   3 #include <iostream>
   4
   5 using namespace std;
   6
   7 struct turtle{
   8   int w,s;
   9   turtle(int W, int S) : w(W), s(S) {}
  10   bool operator < (const turtle &y) const{
  11     return (s - w < y.s - y.w) ||
  12       (s - w == y.s - y.w && w < y.w) ||
  13       (s - w == y.s - y.w && w == y.w && y.s < y.w);
  14   }
  15 };
  16
  17 int main(){
  18   vector<turtle> t;
  19   int x, y;
  20   while (cin >> x >> y){
  21     t.push_back(turtle(x,y));
  22   }
  23   sort(t.begin(), t.end());
  24
  25   /*for (int i=0; i<t.size(); ++i){
  26     cout << "turtle[i]: " << t[i].w << " " << t[i].s;
  27     cout << endl;
  28     }*/
  29
  30   vector<int> p(t.size()), a(t.size());
  31   for (int i=0; i<t.size(); ++i){
  32     a[i] = 1;
  33     p[i] = t[i].w;
  34     for (int j=0; j<i; ++j){
  35       if (t[i].w + p[j] <= t[i].s && a[i] < a[j] + 1){
  36         a[i] = a[j] + 1;
  37         p[i] = p[j] + t[i].w;
  38       }
  39     }
  40   }
  41   cout << *(max_element(a.begin(), a.end())) << endl;
  42   return 0;
  43 }